/**
* Created with IntelliJ IDEA.
* Description:
* User:DELL
* Date:2025-04-19
* Time:22:50
*/
public class Test7 {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n=nums.length;
        tmp=new int[n];
        return mergeSort(nums,0,n-1);
    }
    public int mergeSort(int[] nums,int left,int right){
        if(left>=right){
            return 0;
        }
        int ret=0;
        //根据中间元素，将区间分为两部分
        int mid=(left+right)/2;
        //[left ,mid] [mid+1,right]
        //求出两个区间的翻转对
        ret+=mergeSort(nums,left,mid);
        ret+=mergeSort(nums,mid+1,right);
        //求出一左一右，先计算翻转对
        int cur1=left,cur2=mid+1,i=left;//
        //降序
        while(cur1<=mid){
            while(cur2<=right&&nums[cur1]/2.0<=nums[cur2]) cur2++;
            if(cur2>right)
                break;
            ret+=right-cur2+1;
            cur1++;
        }
        //合并两个数组
        cur1=left;cur2=mid+1;
        while(cur1<=mid&&cur2<=right){
            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];
        }
        while(cur1<=mid){
            tmp[i++]=nums[cur1++];
        }
        while(cur2<=right){
            tmp[i++]=nums[cur2++];
        }
        for(int j=left;j<=right;j++){
            nums[j]=tmp[j];
        }
        return ret;//
    }
}
